import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Dictionary {
	private static final int LEVENSHTEIN_THRESHOLD = 7;
	private static final String SOUNDEX_DIGITS = "01230120022455012623010202";
	private static final int SUGGESTION_COUNT = 4;
	private Set<String> _dictionary;
	private Map<String, List<String>> _soundex;
		
	public Dictionary(String filename) throws IOException {
		BufferedReader in = new BufferedReader(new FileReader(filename));
		
		_dictionary = new HashSet<String>();
		_soundex = new HashMap<String, List<String>>();
		
		String line;
		while((line = in.readLine()) != null) {
			_dictionary.add(line);
			
			String soundexCode = KnuthSoundex(line);
			if(_soundex.containsKey(soundexCode)) {
				_soundex.get(soundexCode).add(line);
			} else {
				List<String> similar = new LinkedList<String>();
				similar.add(line);
				_soundex.put(soundexCode, similar);
			}
		}
		in.close();
	}
	
	/*
	 * Shamelessly stolen from
	 * http://www.ibm.com/developerworks/java/library/j-jazzy/
	 */
	public static String KnuthSoundex(String string) {
		String word = string.toUpperCase();
		word = word.replaceAll("[^A-Z]", "");
		if (word.length() == 0) {
			return "";
		}
		char first = word.charAt(0);
		word = first + word.substring(1).replaceAll("[HW]", "");
		StringBuffer sndx = new StringBuffer();
		for (int i = 0; i < word.length(); i++) {
			sndx.append(SOUNDEX_DIGITS.charAt((int) (word.charAt(i) - 'A')));
		}
		word = sndx.toString().replaceAll("(.)\\1+", "$1");
		word = first + word.substring(1);
		word = word.replaceAll("0", "");
		return (word + "000").substring(0, 4);
	}
	
	public List<Suggestion> getSuggestions(String misspelled, int maxReturnCount) {
		misspelled = sanitize(misspelled);
		List<Suggestion> sug = new ArrayList<Suggestion>();
		List<String> soundexMatches = _soundex.get(KnuthSoundex(misspelled));

		if(soundexMatches == null) return sug;
		
		LevenshteinDistanceMetric l = new LevenshteinDistanceMetric();
		for( String s : soundexMatches ){
			int distance = l.distance(misspelled, s);
			if(distance < LEVENSHTEIN_THRESHOLD){
				sug.add(new Suggestion(s, distance));
			}
		}
		Collections.sort(sug);
		return sug.subList(0, 
			((sug.size() <= maxReturnCount)? sug.size() : maxReturnCount)
		);
	}
	
	public List<Suggestion> getSuggestions(String misspelled) {
		return getSuggestions(misspelled, SUGGESTION_COUNT);
	}
	
	public boolean contains(String word) {	
		return _dictionary.contains(
			sanitize(word)
		);
	}
	
	private String sanitize(String word) {
		String result = word.toLowerCase();
		
		Pattern pat = Pattern.compile("(\\w+)");
		Matcher m = pat.matcher(result);
		
		if(m.find()) {
			result = m.group();
		}
		
		return result;
	}
}
